#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int data_Type;
//队列类型 结构体
typedef struct Node
{
    data_Type data;//数据域
    struct Node *next;//指针域
} Node,*pNode;
typedef struct LinkQueue
{
    pNode front;//队头
    pNode rear;//队尾
} LinkQueue;
LinkQueue *init_LinkQueue();//初始化
int push_LinkQueue(LinkQueue *queue, data_Type value);//入队
int  pop_LinkQueue(LinkQueue *queue,data_Type *value);//出队
int empty_LinkQueue(LinkQueue *queue);//判空
data_Type front_LinkQueue(LinkQueue *queue);//取队头元素
data_Type back_LinkQueue(LinkQueue *queue);//取队尾元素
void clear_LinkQueue(LinkQueue *queue);//清空
void output_LinkQueue(LinkQueue *queue);//输出
int size_LinkQueue(LinkQueue *queue);//大小
void destory_LinkQueue(LinkQueue **queue);//销毁
int main(int argc, char const *argv[])
{
   //初始化
   LinkQueue *lkq=init_LinkQueue();
   //入队
   printf("入队：1 2 3 4 \n");
   if(!push_LinkQueue(lkq,1));else printf("push error\n");
   if(!push_LinkQueue(lkq,2));else printf("push error\n");
   if(!push_LinkQueue(lkq,3));else printf("push error\n");
   if(!push_LinkQueue(lkq,4));else printf("push error\n");
   //
   printf("对头元素值：%d 队尾元素值：%d\n",front_LinkQueue(lkq),back_LinkQueue(lkq));
   //出队
   data_Type dat;
   if(!pop_LinkQueue(lkq,&dat))printf("出队：%d\n",dat);else printf("pup error\n");
   if(!pop_LinkQueue(lkq,&dat))printf("出队：%d\n",dat);else printf("pup error\n");
   //再次入队
   printf("再次入队 100  200");
   if(!push_LinkQueue(lkq,100));else printf("push error\n");
   if(!push_LinkQueue(lkq,200));else printf("push error\n");
    //输出
    output_LinkQueue(lkq);
   //清空 
  // clear_LinkQueue(lkq);

   //长度
   int len=size_LinkQueue(lkq);
   printf("size:%d\n",len);
   //再次出队
   if(!pop_LinkQueue(lkq,&dat))printf("出队：%d\n",dat);else printf("pup error\n");
   if(!pop_LinkQueue(lkq,&dat))printf("出队：%d\n",dat);else printf("pup error\n");
   if(!pop_LinkQueue(lkq,&dat))printf("出队：%d\n",dat);else printf("pup error\n");
   if(!pop_LinkQueue(lkq,&dat))printf("出队：%d\n",dat);else printf("pup error\n");
 
    //销毁
     destory_LinkQueue(&lkq);
     printf("销毁后入队测试：1 \n");
     if(!push_LinkQueue(lkq,1));else printf("push error\n");

    return 0;
}
//初始化
LinkQueue *init_LinkQueue()
{
    LinkQueue *lkqueue =(LinkQueue*)malloc(sizeof(LinkQueue));//为了存储 对头和队尾指针 去分配一段空间
    if(lkqueue==NULL)
    {
        printf("malloc faild\n");
        return NULL;
    }
    //由于前面还只是给两个指针  创建了一个空间  那实际头结点 还没有  也就是这两个指针还没有指向
    pNode head=(pNode)malloc(sizeof(Node));
    if(head==NULL)
    {
        //释放原来为两个指针开辟的空间
        free(lkqueue);
        //
        printf("malloc faild2\n");
        return NULL;
    }
    //头结点  不存放数据
    head->data=-1;//这个数据随便给
    //是一个空队列
    lkqueue->front=lkqueue->rear=head;

    //头结点的next为空
    lkqueue->front->next=NULL;
    return lkqueue;

}
//入队
int push_LinkQueue(LinkQueue *queue, data_Type value)
{
    if(queue==NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if(queue->front==NULL)
    {
        printf("stack is null\n");
        return -1; 
    }
    if(queue->rear==NULL)
    {
        printf("stack is null2\n");
        return -1; 
    }
    //创建一个结点
    pNode newnode=(pNode)malloc(sizeof(Node));//
    if(newnode==NULL)
    {
        printf("newmnode malloc faild\n");
        return -1;
    }
    //更新数据
    newnode->data=value;
    newnode->next=NULL;
    //修改指针
    queue->rear->next=newnode;//将新节点插在后面
    queue->rear=newnode;//更新尾部指针
    return 0;  
}
//出队
int  pop_LinkQueue(LinkQueue *queue,data_Type *value)
{
    if(queue==NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if(queue->front==NULL)
    {
        printf("queue is null\n");
        return -1; 
    }
    if(queue->rear==NULL)
    {
        printf("queue is null2\n");
        return -1; 
    }
    if(queue->front==queue->rear)
    {
        printf("queue is empty\n");
        return -1; 
    }
    //先保存要出去的数据的结点  因为后续要释放
    pNode t=queue->front->next;//保存第一个结点
    queue->front->next=t->next;//更新新的结点
    //如果现在t是唯一的一个数据 t就是队尾  队尾指针将会变成一个野指针  如果出队当前这个元素，队列应该为空队列
    if(t==queue->rear)
    {
        queue->rear=queue->front;//重新指向头结点
    }

    *value=t->data;//将值取出
    free(t);//释放
    return 0;

}
//判空
int empty_LinkQueue(LinkQueue *queue)
{
    return queue->rear==queue->front;
}
//取队头元素
data_Type front_LinkQueue(LinkQueue *queue)
{
    if(queue==NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if(queue->front==NULL)
    {
        printf("queue is null\n");
        return -1; 
    }
    if(queue->rear==NULL)
    {
        printf("queue is null2\n");
        return -1; 
    }
    if(queue->front==queue->rear)//空队  指向头结点
    {
        printf("queue is empty\n");
        return -1; 
    }

    return queue->front->next->data;//因为queue->front指向的是头结点  头结点是部分存放数据的

}
//取队尾元素
data_Type back_LinkQueue(LinkQueue *queue)
{
    if(queue==NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if(queue->front==NULL)
    {
        printf("queue is null\n");
        return -1; 
    }
    if(queue->rear==NULL)
    {
        printf("queue is null2\n");
        return -1; 
    }
    if(queue->front==queue->rear)//空队  指向头结点
    {
        printf("queue is empty\n");
        return -1; 
    }
    return queue->rear->data;//queue->rear指向的就是队尾元素

}
//清空  清空队列中的数据结点 
void clear_LinkQueue(LinkQueue *queue)
{
    if(queue==NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if(queue->front==NULL)
    {
        printf("stack is null\n");
        return -1; 
    }
    if(queue->rear==NULL)
    {
        printf("stack is null2\n");
        return -1; 
    }
    if(empty_LinkQueue(queue))
    {
        return;
    }
    pNode t=queue->front->next;//从头结点的第一个数据元素开始删除 队头
    while(t!=NULL)
    {
        //更新新的队头
        queue->front->next=t->next;
        printf("clear data:%d\n",t->data);
        free(t);
        t=queue->front->next;
    }
    //将队头和队尾 同时指向  head
    queue->rear=queue->front;

}
//输出
void output_LinkQueue(LinkQueue *queue)
{
    if(queue==NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if(queue->front==NULL)
    {
        printf("stack is null\n");
        return -1; 
    }
    if(queue->rear==NULL)
    {
        printf("stack is null2\n");
        return -1; 
    }
    if(empty_LinkQueue(queue))
    {
        return;
    }
    pNode t=queue->front->next;//从头结点的第一个数据元素开始删除 队头
    printf("队列遍历：\n");
    while(t!=NULL)
    {
        printf("%d ",t->data);
        t=t->next;
    }
    printf("\n");
}
//大小
int size_LinkQueue(LinkQueue *queue)
{
    if(queue==NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if(queue->front==NULL)
    {
        printf("stack is null\n");
        return -1; 
    }
    if(queue->rear==NULL)
    {
        printf("stack is null2\n");
        return -1; 
    }
    if(empty_LinkQueue(queue))
    {
        return 0;
    }
    int i=0;
    pNode t=queue->front->next;//从头结点的第一个数据元素开始删除 队头
    while(t!=NULL)
    {
       i++;
        t=t->next;
    }
    return i;

}
//销毁
void destory_LinkQueue(LinkQueue **queue)
{
    if((*queue)==NULL)
    {
        printf("queue is error\n");
        return ;
    }
    if((*queue)->front==NULL)
    {
        printf("queue is null\n");
        return ; 
    }
    if((*queue)->rear==NULL)
    {
        printf("queue is null2\n");
        return ; 
    }
    clear_LinkQueue(*queue);//先清空  
    free((*queue)->front);//就是queue->rear  就是头结点
    free(*queue);
    *queue=NULL;

}